package number_operatation.leetcode.easy;

/**
 * @author bruin_du
 * @description 整数除法
 * @date 2022/7/30 23:57
 **/
public class OfferII001_Divide {
    public int divide(int a, int b) {
        if (a == 0 || b == 0) {
            return 0;
        }
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }
        if (b == Integer.MIN_VALUE) {
            if (a == Integer.MIN_VALUE) return 1;
            else return 0;
        }
        //为了统一符号，都变为负数
        //变为负数是因为-2^31变为正数会越界,变为负数就不会
        //但是后面进行判断大小时的不等号要取反
        boolean flag = true;
        if (a > 0) {
            a = -a;
            flag = !flag;
        }
        if (b > 0) {
            b = -b;
            flag = !flag;
        }
        int res = 0;
        //用的时快速幂进行修改得到的快速乘
        //但是不能利用比特位一次遍历,需要两次log的判断
        //外层循环是看是否减完,里层是找到能减去的最大倍数的除数
        while (a <= b) {
            int x = b;
            int k = 1;
            //这里不能x + x,会越界,需要相减
            while (a - x <= x) {
                x += x;
                k <<= 1;
            }
            a -= x;
            res += k;
        }
        return flag ? res : -res;
    }
}
